翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

说明：

  • 无空格字符构成一个 单词 。
  • 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

示例 1：

1
2
输入："the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入："  hello world!  "
输出："world! hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

1
2
3
输入："a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

示例 4：

1
2
输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"

示例 5：

1
2
输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"

提示：

  1. 1 <= s.length <= 104
  2. s 包含英文大小写字母、数字和空格 ‘ ‘
  3. s 中 至少存在一个 单词

进阶：

请尝试使用 O(1) 额外空间复杂度的原地解法。

代码:

第一次提交（通过，但时空不够，采用的是原地解法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public String reverseWords(String s) {
        //将多余的空格去除
        StringBuffer sb=new StringBuffer(s.replaceAll(" +"," ").trim());
        //整个字符串反转
        sb.reverse();

        //窗口指针
        int i=-1,j=0;
        for(;j<sb.length();j++)
        {
            //如果i是负一，且遇到非0字符,把i设定为窗口头
            if(i==-1&&sb.charAt(j)!=' ')
            {
                i=j;
            }
            //要是找到空格，或者已经到了最后一个字符，就在i-(j-1)的窗口范围里反转
            if(i!=-1&&(sb.charAt(j)==' '||j==sb.length()-1))
            {
                if(j==sb.length()-1)j++;
                for(int k=0;k<(j-i)/2;k++)
                {
                    char c1=sb.charAt(i+k);
                    char c2=sb.charAt(j-1-k);
                    sb.replace(i+k,i+k+1,String.valueOf(c2));
                    sb.replace(j-1-k,j-1-k+1,String.valueOf(c1));
                }
                i=-1;
            }

        }
        return sb.toString();
    }
}

第二次提交（77%时，94%空）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public String reverseWords(String s) {
        if(s == null || s.length() == 0) {
            return s;
        }
        char[] str=new char[s.length()];
        //将多余的空格去除
        //反转整个字符串
        int cur=0;
        //-1即头尾空格，不需要添加
        int flag=-1;
        for(int i=s.length()-1;i>=0;i--)
        {
            char temp=s.charAt(i);
            if(temp!=' ')
            {
                if(flag==1)
                    str[cur++]=' ';
                flag=0;
                str[cur++]=temp;
            }
            if(temp==' '&&flag==0)
            {
                flag=1;
            }
        }
        //窗口指针
        int i=-1,j=0;
        for(;j<cur;j++)
        {
            //如果i是负一，且遇到非0字符,把i设定为窗口头
            if(i==-1&&str[j]!=' ')
            {
                i=j;
            }
            //要是找到空格，或者已经到了最后一个字符，就在i-(j-1)的窗口范围里反转
            if(i!=-1&&(str[j]==' '||j==cur-1))
            {
                if(j==cur-1)j++;
                for(int k=0;k<(j-i)/2;k++)
                {
                    char temp=str[i+k];
                    str[i+k]=str[j-1-k];
                    str[j-1-k]=temp;
                }
                i=-1;
            }

        }
        return new String(str,0,cur);
    }
}